package myjava.algorithm;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

public class WordLadder {
    public int ladderLength(String start, String end, Set<String> dict) {
    	if (dict.size() == 0)  
            return 0;
    	
    	LinkedList<String> queue = new LinkedList<String>();
    	LinkedList<Integer> distant = new LinkedList<Integer>();
    	queue.add(start);
    	distant.add(1);
    	
    	int min = 0;
    	
    	while(!queue.isEmpty())
    	{
    		String e = queue.pop();
    		int d = distant.pop();
    		
    		if(e.equals(end))
    			return d;

    		
    		
    		for(int i= 0;i<e.length();i++)
    		{
    			char[] charArray = e.toCharArray();
    			
    			for(char a = 'a';a <= 'z';a++)
        		{
        			charArray[i]=a;
        			
        			String tempString = new String(charArray);
        			
        			if(dict.contains(tempString))
        			{
        				queue.add(tempString);
        				distant.add(d + 1);
        				dict.remove(tempString);
        			}
        			else if(tempString.equals(end))
        			{
        				if(min == 0 && (d+1)> min)
        				{
        					min = d+1;
        				}
        				else if(min > (d+1))
        					min = d+1;
        			}
        		}
    		}   		
    	}
    	
    	return min;
    }
    

	public static void main(String[] args) {
		 Set<String> dict = new HashSet<String>();
		 dict.add("hot");
		 dict.add("dot");
		 //dict.add("dog");
		 dict.add("lot");
		 dict.add("lom");
		 dict.add("lim");
		 dict.add("lok");
		 dict.add("log");
		 
		 WordLadder w = new WordLadder();
		 
		 System.out.println(w.ladderLength("hit","cog",dict));
	}

}

class GraphNode
{
	String a;
	int distant;
	
	public GraphNode(String word,int dist)
	{
		a = word;
		distant = dist;
	}
	
	public String GetString()
	{
		return a;
	}
	
	public int GetDistant()
	{
		return distant;
	}
	
	public void SetDistant(int x)
	{
		distant = x;
	}
}




